home *** CD-ROM | disk | FTP | other *** search
/ The PC-SIG Library 10 / The PC-Sig Library - Shareware for the IBM PC and Compatibles (PC-SIG)(Tenth Edition Disks 1-2804)(1991).iso / PC_SIGCD / 07 / 3 / DISK0731.ZIP / INDEXREF < prev    next >
Text File  |  1987-02-09  |  6KB  |  123 lines
  1. REFERENCE                INDEX(2)
  2.  
  3.  
  4. INDEX generates what is technically called an "inverted index".  
  5. Whereas, the disk itself is organized as "files containing words", 
  6. the index is organized as "words containing files".  While the 
  7. notion is simple, the implementation is faced with many issues.
  8.  
  9. The largest issue is one of space.  A simple list of words with 
  10. each file name containing the word and a sub list of file names 
  11. would be many times the size of the data to be indexed.  The 
  12. first economy of space is to build a map of file names to file 
  13. numbers.  Thus a two byte file number can stand for each instance 
  14. of a file name in the index.
  15.  
  16. File names are technically restricted to 64 characters.  In 
  17. practice, they are much shorter.  Still the use of hierarchical 
  18. directories requires a list of directory names to describe the 
  19. path to a file.  INDEX builds a "map" which links file names to 
  20. directory names in the path.
  21.  
  22. To attack the space problem further, the list of words itself 
  23. must be attacked.  First, INDEX, deals only with letters.  No 
  24. digits or punctuation are indexed.  Second, case is ignored.  All 
  25. lower case letters are converted to upper case.  Third, words 
  26. less than 3 characters in length are discarded and words greater 
  27. than 7 characters in length are significant only in the first 7 
  28. characters.  Fourth, each word is discarded if it appears in the 
  29. list of "common" words.  Each of these methods gives up something 
  30. in the retrieval phase to reduce the size of the index.
  31.  
  32. Still, the list of unique words indexed is large.  Acronyms and
  33. proper names added to "normal" words add up to perhaps hundreds 
  34. of thousands of possible words.  The memory size of most personal 
  35. computers limits the number of words in memory to tens of 
  36. thousands words at best.  
  37.  
  38. The second issue is one of speed.  Unless indexing were performed 
  39. at an operating system level, an index can only represent the 
  40. state of the disk at one particular time.  Thus it becomes 
  41. necessary to re-index data periodically.  While microcomputer 
  42. systems are idle substantial periods of time, it is desirable to 
  43. index quickly.  Retrieval requires that the list of files 
  44. associated with a key word be accessible quickly as well.
  45.  
  46. INDEX thus makes the assumption that there are only 4093 unique 
  47. words.  To reduce the set of unique words to 4093, a mathematical 
  48. operation (called hashing) is applied to each word generating a 
  49. number which is then divided by 4093, the remainder standing for 
  50. the word.  Further, even though a file may contain many instances 
  51. of keywords generating a particular number, only one such 
  52. instance needs to be recorded.  This greatly reduces the space 
  53. and time required to generate an inverted index.  The problem 
  54. created by this assumption is that two different keywords may 
  55. generate the same number.  Fortunately, statistics are on our 
  56. side and when two or more keywords are used for a retrieval, the 
  57. probability of two files containing keywords generating the same 
  58. numbers is small.
  59.  
  60. Consequently, INDEX generates a file containing one entry for 
  61. each unique keyword number which in turn points to a file 
  62. containing one file number for each unique keyword number, file 
  63. number pair.
  64.  
  65. The following is a general description of the program flow.
  66.  
  67. INDEX performs initialization, scans the current directory, and 
  68. then wraps up.
  69.  
  70. Initialization consists of writing the copyright notice and 
  71. version, processing the parameters, initializing global 
  72. variables, reading the EXTENSIO.INX file, reading the WORD.INX 
  73. file and finally initializing output files (MAP.INX, ENTRY.INX, 
  74. and KEY.INX).
  75.  
  76. To scan the current directory, the MS-DOS function "find first 
  77. file" is issued.  If that is successful, the file name is parsed 
  78. and the file is analyzed.  While successive calls to "find next 
  79. file" are successful, each file is analyzed.
  80.  
  81. To analyze a file, the directory is checked to determine if the 
  82. file is a directory or a file.  If it is a directory and is not 
  83. "." or ".." then a "change directory" is performed and the new 
  84. directory is scanned recursively.  The nesting level is 
  85. incremented each time a sub-directory is encountered and 
  86. decremented as each directory scan is completed.  Each directory 
  87. scanned generates an entry into the MAP.INX file.
  88.  
  89. If a file is not a directory (i.e. is an ordinary file) and its 
  90. extension is not found in the list of excludable extensions, it 
  91. is added to MAP.INX pointing back to the parent directory.  The 
  92. file name is displayed on the console and then the file itself is 
  93. scanned.
  94.  
  95. To scan a file, a new ordered lists of codes is created and 
  96. initialized (unless this is a second or subsequent pass in which 
  97. case a list is reused).  After the file is opened, it is scanned 
  98. as blocks of characters.  Any type of file (i.e. code, data, 
  99. text, etc...) is treated the same way.  Lower case letters are 
  100. converted to upper case.  File scanning has two states; either it 
  101. is assembling a word or it is not.  If it is not assembling 
  102. words, characters are ignored until a letter is encountered in 
  103. which case it switches state.  If it is assembling words, each 
  104. letter encountered effects a mathematical operation which 
  105. generates a number.  
  106.  
  107. Finding a non letter terminates assembly of the word.  The word 
  108. is searched in the common word list.  If found, the word is 
  109. discarded and the scan continues.  If not found the number is 
  110. folded onto the range of distinct words and the code for the word 
  111. is entered into a sorted list.  Scanning continues until the end 
  112. of file is reached.  Upon reaching the end of a file, a lack of 
  113. memory will trigger writing or updating the index file.
  114.  
  115. Wrapup consists of writing an index, closing the files, and 
  116. producing a brief report.  Writing the index requires inverting 
  117. the collected data which was collected and file order but needs 
  118. to be retrieved in keyword code order.  For each possible keyword 
  119. code the list by file of keyword codes is scanned.  Each file 
  120. containing the current keyword code is written to KEY.INX.  At 
  121. the end of each keyword code the current position in KEY.INX is 
  122. written to ENTRY.INX.
  123.